// https://leetcode.cn/problems/find-bottom-left-tree-value/

// [3,1,5,0,2,4,6] 
/*
	 3
  1     5
0   2 4   6
*/

#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	int leftVal;
	int flag = 0;
    int findBottomLeftValue(TreeNode* root) {
		leftVal = root->val;
		int height = getHeight(root);
		back(root, 1, height);
		return leftVal;
    }
	
	void back(TreeNode * head, int index, int height){
		if(head){
			// cout << index << " " << height << endl;
			if(index == height && flag == 0){
				// cout << head->val << endl;
				leftVal = head->val;
				flag = 1;
				return;
			}
			// if(head->left && index == height){
				// leftVal = head->left->val;
				
				// return;
			// }else if(head->right && index == height){
				// leftVal = head->right->val;
				// cout << "leftVal: " << leftVal << endl;
				// return;
			// }
			back(head->left, index + 1, height);
			back(head->right, index + 1, height);
		}
	}
	
	int getHeight(TreeNode * head){
		if(!head){
			return 0;
		}
		return max(getHeight(head->left), getHeight(head->right)) + 1;
	}
};

int main(){
	Solution so;
	TreeNode * head = new TreeNode(3);
	TreeNode * left = new TreeNode(1);
	TreeNode * right = new TreeNode(5);
	TreeNode * i1 = new TreeNode(0);
	TreeNode * i2 = new TreeNode(2);
	TreeNode * i3 = new TreeNode(4);
	TreeNode * i4 = new TreeNode(6);
	
	head->left = left;
	head->right = right;
	left->left = i1;
	left->right = i2;
	right->left = i3;
	right->right = i4;
	int a = so.findBottomLeftValue(head);
	cout << a << endl;
	
	return 0;
}